In recent years, different cryptanalysis methods for analyzing encryption keys using side information when encryption modules implemented in hardware or software perform encryption processing have been formulated. For instance, in an analysis method called a timing attack, an encryption key is analyzed by using a fact that a time required for an encryption module to perform encryption processing slightly varies according to a value of the encryption key being used in the encryption processing. To put it differently, in the timing attack, cryptanalysis of the encryption key is performed using side information that is a processing time when performing the encryption processing. Among those cryptanalysis methods, different methods such as a simple power analysis and a differential power analysis have been formulated as cryptanalysis methods for performing cryptanalysis using, as side information, power consumption when performing encryption processing. It has been reported that the methods of cryptanalysis can be used to analyze an actual product, such as an IC card, in which a cipher is implemented, partly because high-performance measuring devices have recently become available at a low price. Furthermore, a great number of analysis methods, such as a method for performing cryptanalysis using, as side information, the strength of an electromagnetic wave generated in an encryption module when performing encryption processing, have been formulated. In the following description, cryptanalysis methods for analyzing encryption keys using power consumption of encryption modules when performing encryption processing are collectively called a “power analysis attack”. Although the following gives a description using the power analysis attack as an example, the present invention is also effective for other analysis methods in which side information is used. In other words, the present invention can be applied to not only the power analysis attack but also analysis methods for inferring keys using side information generated in encryption modules during encryption processing.
The power analysis attack performs a key analysis using a correlation between power consumption of an encryption module and an intermediate value in encryption processing. Thus, as a countermeasure for the power analysis attack, it is thought that the correlation between the power consumption and the intermediate value in encryption processing is obscured by randomizing the intermediate value with a random number generated in the encryption module. Randomizing the intermediate value in encryption processing in the above manner is called “masking” the intermediate value. Moreover, methods for making the key analysis of the power analysis attack difficult by masking the intermediate value are collectively called a “masking method”.
Patent Reference 1 discloses the masking method (hereinafter referred to as Conventional Technique 1) for the U.S. Data Encryption Standard (DES) cipher.
(Summary of Conventional Technique 1)
According to Conventional Technique 1, a randomized Sbox table in which a table Sbox for data conversion used for the DES cipher is randomized based on a random number generated in an encryption module is created prior to encryption processing and temporarily stored. Using the randomized Sbox table allows an intermediate value for encryption processing to be masked, which makes power analysis attack difficult. Here, in Conventional Technique 1, a RAM for temporarily storing the randomized Sbox table is needed. Thus, in the case where there are strict limits on RAM capacity, there is a problem that Conventional Technique 1 cannot be used. Moreover, in the case where the encryption module is implemented in hardware, an Sbox table is generally implemented in a logic circuit. Thus, since the randomized Sbox table cannot be created, there is a problem that Conventional Technique 1 cannot be used.
(Summary of Conventional Technique 2)
Non-patent Reference 1 discloses a masking method (hereinafter referred to as Conventional Technique 2) for the U.S. Advanced Encryption Standard (AES) cipher. Since the Sbox table can be implemented in the logic circuit and, as with Conventional Technique 1, the randomized Sbox table does not need to be created, Conventional Technique 2 is suitable for hardware implementation. The following will describe the summary of Conventional Technique 2.
It is known that an inverse element calculation (“X^Y” indicates “raising X to the Y power”) in an extension field GF(2^8) and processing in which predetermined affine transformation is preformed are equivalent in an Sbox table for AES cipher. In addition, an example of methods for implementing in a circuit the inverse element calculation for an element X in the extension field GF(2^8) includes the following existing method.
(1) Transform X into an element A in a composite field GF(((2^2)^2)^2) that is the same type as GF(2^8).
(2) Calculate an inverse element A^(−1) of A in the composite field.
(3) Inversely transform A^(−1) into an element in an extension field to obtain X^(−1).
In this method, it is possible to implement the inverse element calculation with a small circuit size by performing the inverse element calculation in the composite field.
When the Sbox table for AES cipher is implemented through the above inverse element calculation and affine transformation and a masking method is applied to the Sbox table for AES cipher, it is possible to increase a resistance to the power analysis attack with the small circuit size. At this time, a point is how a portion of the inverse element calculation is masked. The following will briefly describe the masking method for the portion of the inverse element calculation in Conventional Technique 2.
FIGS. 1 to 7 show a randomized 8-bit inverse element calculation unit 81 included in an encryption device according to Conventional Technique 2.
<Randomized 8-Bit Inverse Element Calculation Unit 81>
FIG. 1 is a block diagram showing a configuration of the randomized inverse element calculation unit 81 according to Conventional Technique 2. The randomized 8-bit inverse element calculation unit 81 performs an inverse element calculation using, as inputs, masked data X (8 bits) that is an object of the inverse element calculation, mask data R (8 bits), a random number for calculation r (4 bits), and outputs the masked result of the inverse element calculation Y (8 bits). Here, X is data that has been masked with the mask data R, and expressed as X=M(+)R. Here, M (8 bits) is data that has not been masked, and “(+)” indicates a bit-basis exclusive OR operation. Y is expressed as Y={M^(−1)}(+)R. In other words, the randomized 8-bit inverse element calculation unit 81 performs the inverse element calculation using, as an input, M that has been masked by R, and accordingly outputs M^(−1) that is masked with R. Stated differently, since the inverse element calculation is performed on M that is an intermediate value for encryption processing with M masked with the random mask data R, power analysis attack is difficult to execute.
As shown in FIG. 1, the randomized 8-bit inverse element calculation unit 81 includes seventeenth power calculation units 810 and 812 that perform a seventeenth power calculation in a composite field GF(((2^2)^2)^2), a 4-bit correction term calculation unit 811 (FIG. 2), 4-bit output calculation units 816 and 817 (FIG. 3), exclusive OR units 813, 814, 818, and 819 that perform a 4-bit exclusive OR operation, and a randomized 4-bit inverse element calculation unit 815 (FIG. 4).
Here, as shown in FIG. 2, the 4-bit correction term calculation unit 811 includes 4-bit multiplication units 811a and 811b that perform a multiplication in a composite field GF((2^2)^2), and exclusive OR units 811c and 811d that perform the 4-bit exclusive OR operation. It is to be noted that the composite field GF (((2^2)^2)^2) is a secondary extended composite field GF ((2^2)^2).
Furthermore, as shown in FIG. 3, the 4-bit output calculation units 816 and 817 each include 4-bit multiplication units 816a to 816d that perform the multiplication in the composite field GF((2^2)^2), and exclusive OR units 816e to 816j that perform the 4-bit exclusive OR operation.
Moreover, as shown in FIG. 4, the randomized 4-bit inverse element calculation unit 815 includes fifth power calculation units 820 and 822 that perform a fifth power calculation in the composite field GF((2^2)^2), a 2-bit correction term calculation unit 821 (FIG. 5), 2-bit output calculation units 826 and 827 (FIG. 6), exclusive OR units 823, 824, 828, and 829 that perform a 2-bit exclusive OR operation, and a randomized 2-bit inverse element calculation unit 825 (FIG. 7).
Here, as shown in FIG. 5, the 2-bit correction term calculation unit 821 (FIGS. 4 and 5) includes 2-bit multiplication units 821a and 821b that perform a multiplication in a finite field GF(2^2), and exclusive OR units 821c and 821d that perform the 2-bit exclusive OR operation. It is to be noted that the composite field GF((2^2)^2) is a secondary extended finite field GF(2^2).
In addition, as shown in FIG. 6, the 2-bit output calculation units 826 and 827 (FIGS. 4 and 6) each include 2-bit multiplication units 826a to 826d that perform the multiplication in the finite field GF(2^2), and exclusive OR units 826e to 826j that perform the 2-bit exclusive OR operation.
Furthermore, as shown in FIG. 7, the randomized 2-bit inverse element calculation unit 825 (FIGS. 4 and 7) includes exclusive OR units 825a and 825b that perform a 1-bit exclusive OR operation.
As described above, the randomized 8-bit inverse element calculation unit 81 (FIG. 1) that is provided to the encryption device according to Conventional Technique 2 is configured to cause recursively the randomized 4-bit inverse element calculation unit 815 and the randomized 2-bit inverse element calculation unit 825 to operate. Due to this configuration implementation is possible with a relatively smaller circuit size, in comparison with other conventional techniques.
Conventional Technique 2 discloses the encryption device that is designed to be suitable for hardware implementation by providing the randomized 8-bit inverse element calculation unit 81 (FIG. 1) so as to implement the Sbox table for AES cipher through the inverse element calculation and the affine transformation.    Non-patent Reference 1: Morioka, Sumio & Toru Akishita. (October, 2004). DPA attack to AES S-Box Circuits over Composite Fields. Computer Security Symposium 2004 Preliminary Report, 679-684.    Non-patent Reference 2: Federal Information Processing Standards Publication 197, Specification for the ADVANCED ENCRYPTION STANDARD (AES), Nov. 26, 2001    Patent Reference 1: U.S. Pat. No. 6,295,606